9016. Бинарный
поиск
Задан отсортированный массив из n целых чисел. Необходимо ответить
на q запросов: содержится ли заданное
число x в массиве.
Вход. Первая
строка содержит два целых числа n и q (n,
q ≤ 106). Вторая
строка содержит n целых чисел,
отсортированных по возрастанию. Каждая из следующих q строк содержит одно число x.
Все числа в массиве по модулю не превышают 109.
Выход. Для каждого запроса выведите в
отдельной строке “YES”, если число x присутствует в
массиве, и “NO” в противном случае.
|
Пример
входа 1 |
Пример
выхода 1 |
|
6 3 2 4 4 8 11 14 10 4 2 |
NO YES YES |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
8 4 -8 -8 -1 1 3 4 6 8 4 10 -4 -8 |
YES NO NO YES |
РЕШЕНИЕ
бинарный
поиск
Анализ алгоритма
В данной задаче требуется найти число в
отсортированном массиве, что можно сделать с помощью бинарного поиска.
Пусть m –
отсортированный массив длины n, состоящий из целых чисел. Функция binary_search(m, m + n, x) возвращает true, если число x присутствует в массиве. Входной массив читается за O(n), q запросов выполняются за O(qlog2n).
Функция lower_bound возвращает указатель на первую
позицию, в которую можно вставить элемент x без нарушения свойства
отсортированности массива.
Функция upper_bound возвращает
указатель на последнюю позицию, в которую можно вставить элемент x без
нарушения свойства отсортированности массива.
Если lower_bound(m, m + n, x)
≠ upper_bound(m, m + n,
x), то число x присутствует в массиве. В противном случае числа x в массиве нет.
Java функция Arrays.binarySearch() возвращает индекс найденного элемента в массиве. Если
массив содержит несколько одинаковых ключей, то возвращается индекс любого из них.
Если x отсутствует в
массиве m, то функция Arrays.binarySearch(m, x) возвращает значение –pos – 1, где pos – индекс первого элемента, большего
x. Если x больше всех элементов массива m, то pos = m.length.
Функция bisect в Python
используется для выполнения бинарного поиска в отсортированных
последовательностях. Она помогает найти место вставки элемента в
отсортированный список, чтобы сохранить порядок сортировки. Это может быть
полезно, например, для оптимизации добавления новых элементов в упорядоченный
список или для определения, куда вставить элемент в массив, чтобы сохранить
сортировку.
bisect предоставляет две основные
функции:
·
bisect.bisect_left(lst, x, lo = 0, hi = len(lst)).
Эта функция находит точку вставки для элемента x в отсортированном
списке lst. Если элемент уже присутствует в списке, то bisect_left
вернет индекс первого вхождения x. Если элемент отсутствует, функция
вернет индекс, где можно вставить x, не нарушив порядок сортировки.
·
bisect.bisect_right(lst, x, lo = 0, hi = len(lst)).
Аналогична bisect_left, но возвращает индекс для вставки элемента
x после существующих вхождений x в список lst.
Обе функции принимают
необязательные аргументы lo и hi, которые определяют диапазон
поиска в списке. По умолчанию lo = 0, а hi = len(lst).
Реализация собственного бинарного
поиска.
Пусть требуется найти элемент x в массиве m на промежутке [start; end]. Делим отрезок пополам, положим mid = (start + end) / 2. Если x > m[mid],
то элемент x находится на отрезке [mid + 1; end]. Иначе следует продолжить поиск на отрезке [start;
mid].
Структура данных set. Занесем числа из входного
массива в структуру данных set<int> s. Если некоторое число
присутствует в массиве несколько раз, в set оно будет добавлено только один
раз. При этом результат запроса на присутствие заданного элемента в массиве не
изменится.
Элемент x присутствует во множестве (во входном массиве), если s.find(x) != s.end().
Элементы входного массива
заносятся во множество за O(nlog2n), q
запросов выполняются за O(qlog2n).
Реализация алгоритма – O(n + qlog2n)
Объявим рабочий массив.
#define MAX
1000000
int m[MAX];
Читаем входные данные.
scanf("%d %d",
&n, &q);
for (i = 0; i < n; i++)
scanf("%d",
&m[i]);
Последовательно обрабатываем q запросов.
for (i = 0; i < q; i++)
{
Читаем
число x.
scanf("%d",
&x);
Число x присутствует в массиве m, если функция binary_search возвращает true.
if
(binary_search(m, m + n, x) == 1)
puts("YES");
else
puts("NO");
}
Реализация алгоритма – lower_bound,
upper_bound
Объявим рабочий массив.
#define MAX
1000000
int m[MAX];
Читаем входные данные.
scanf("%d %d",
&n, &q);
for (i = 0; i < n; i++)
scanf("%d",
&m[i]);
Последовательно обрабатываем q запросов.
for (i = 0; i < q; i++)
{
Читаем
число x.
scanf("%d",
&x);
Число x присутствует в массиве m, если
lower_bound(m, m + n, x)
≠ upper_bound(m, m + n,
x)
if
(lower_bound(m, m + n, x) != upper_bound(m, m + n, x))
puts("YES");
else
puts("NO");
}
Реализация алгоритма –
собственный бинарный поиск
Объявим рабочий массив.
#define MAX 1000000
int m[MAX];
Функция my_bin_search реализует бинарный
поиск и возвращает 1, если число x присутствует в массиве m в диапазоне [start;
end].
int my_bin_search(int *m, int start, int end, int x)
{
Запускаем бинарный поиск на интервале [start;
end].
while
(start < end)
{
int mid
= (start + end) / 2;
if (x
> m[mid])
start
= mid + 1;
else
end =
mid;
}
Возвращаем результат.
return
m[start] == x;
}
Основная часть программы. Читаем
входные данные.
scanf("%d %d",
&n, &q);
for (i = 0; i < n; i++)
scanf("%d",
&m[i]);
Последовательно обрабатываем q запросов.
for (i = 0; i < q; i++)
{
Читаем
число x.
scanf("%d", &x);
Число x присутствует в массиве m, если my_bin_search возвращает 1.
if (my_bin_search(m, 0, n - 1, x))
puts("YES");
else
puts("NO");
}
Реализация алгоритма – set, O(nlog2n + qlog2n)
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int i, n, q, x;
set<int> s;
int main(void)
{
scanf("%d %d", &n, &q);
for (i = 0; i < n; i++)
{
scanf("%d", &x);
s.insert(x);
}
for (i = 0; i < q; i++)
{
scanf("%d", &x);
if (s.find(x) != s.end())
puts("YES");
else
puts("NO");
}
return 0;
}
Java реализация – собственный бинарный поиск
import java.util.*;
import java.io.*;
public class Main
{
static int my_bin_search(int m[], int start, int end, int x)
{
while (start < end)
{
int mid = (start + end) /
2;
if (x > m[mid])
start = mid + 1;
else
end
= mid;
}
return (m[start] == x) ? 1 :
0;
}
public static void main(String[] args)
{
FastScanner con =
new FastScanner(new
InputStreamReader(System.in));
int n = con.nextInt();
int q = con.nextInt();
int m[] = new int[n];
for(int i = 0; i < n; i++)
m[i]
= con.nextInt();
for(int i = 0; i < q; i++)
{
int x = con.nextInt();
if(my_bin_search(m,0,n-1,x)
== 1)
System.out.println("YES");
else
System.out.println("NO");
}
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new
BufferedReader(reader);
}
public String next()
{
while (st == null ||
!st.hasMoreTokens())
{
try
{
st
= new StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return
Integer.parseInt(next());
}
public double nextDouble()
{
return
Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}
Java реализация – Arrays.binarySearch
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args)
{
FastScanner con =
new FastScanner(new
InputStreamReader(System.in));
int n = con.nextInt();
int q = con.nextInt();
int m[] = new int[n];
for(int i = 0; i < n; i++)
m[i] = con.nextInt();
for(int i = 0; i < q; i++)
{
int x = con.nextInt();
if(Arrays.binarySearch(m, x) >= 0)
System.out.println("YES");
else
System.out.println("NO");
}
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public
FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}
Python реализация
Импортируем
модуль bisect.
import bisect
Читаем входные данные.
n, q = map(int,input().split())
lst = list(map(int,input().split()))
Последовательно обрабатываем q запросов.
for _ in range(q):
Читаем
число x.
x = int(input())
Число x присутствует в массиве m, если
bisect_left(lst, x) ≠ bisect_right(lst, x)
if bisect.bisect_left(lst,
x) != bisect.bisect_right(lst, x):
print("YES")
else:
print("NO")
Python реализация – собственный бинарный
поиск
Функция my_bin_search реализует бинарный поиск:
· если число x отсутствует в списке a, то функция возвращает -1.
· иначе возвращается позиция числа x в списке a.
def my_bin_search(a, x):
start = 0
end = len(a) – 1
Запускаем бинарный
поиск на интервале [start;
end] = [0; len(a) – 1].
while start <
end:
mid = (start + end) // 2;
if x > a[mid]:
start = mid + 1;
else:
end = mid;
if a[start] == x:
return start
else:
return -1;
Основная часть программы. Читаем
входные данные.
n, q = map(int,input().split())
lst = list(map(int,input().split()))
Последовательно обрабатываем q запросов.
for _ in range(q):
Читаем
число x.
x = int(input())
Запускаем бинарный поиск. Выводим соответствующий ответ.
if my_bin_search(lst,x) != -1:
print("YES")
else:
print("NO")